package leo.mystudy.leetcode;

import leo.mystudy.pojo.TreeNode;

/**
 * @author leo
 * @version 1.0.0
 * @description 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
 * <p>
 * 有效 二叉搜索树定义如下：
 * <p>
 * 节点的左子树只包含 小于 当前节点的数。
 * 节点的右子树只包含 大于 当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 *  
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：root = [2,1,3]
 * 输出：true
 * 示例 2：
 * <p>
 * <p>
 * 输入：root = [5,1,4,null,null,3,6]
 * 输出：false
 * 解释：根节点的值是 5 ，但是右子节点的值是 4 。
 *  
 * <p>
 * 提示：
 * <p>
 * 树中节点数目范围在[1, 104] 内
 * -231 <= Node.val <= 231 - 1
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/validate-binary-search-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @create 2022/3/12 18:03
 */
public class No98 {
    public boolean isValidBST(TreeNode root) {
        return doCheck(root, null, null);
    }

    private boolean doCheck(TreeNode root, Integer min, Integer max) {
        if (root == null || (root.left == null && root.right == null)) {
            return true;
        }
        if (!compareChildValue(root, min, max)) {
            return false;
        }
        if (!doCheck(root.left, min, root.val)) {
            return false;
        }
        if (!doCheck(root.right, root.val, max)) {
            return false;
        }
        return true;
    }

    private boolean compareChildValue(TreeNode node, Integer min, Integer max) {
        if (node.left != null) {
            if (node.left.val >= node.val) {
                return false;
            }
        }
        if (node.right != null) {
            if (node.right.val <= node.val) {
                return false;
            }
        }
        if (min != null) {
            if (node.val <= min) {
                return false;
            }
            if (node.left != null && node.left.val <= min) {
                return false;
            }
        }
        if (max != null) {
            if (node.val >= max) {
                return false;
            }
            if (node.right != null && node.right.val >= max) {
                return false;
            }
        }
        return true;
    }

    /**
     * [32,26,47,19,null,null,56,null,27]
     * ------32
     * ---26   47
     * --19 -----56
     * ---27
     *
     * @param args
     */
    public static void main(String[] args) {
//        TreeNode root = new TreeNode(5);
//        root.left = new TreeNode(4);
//        root.right = new TreeNode(6);
//        root.right.left = new TreeNode(3);
//        root.right.right = new TreeNode(7);
        TreeNode root = new TreeNode(32);
        //
        root.left = new TreeNode(26);
        root.right = new TreeNode(47);
        //
        root.left.left = new TreeNode(19);
        root.right.right = new TreeNode(56);
        //
        root.left.left.right = new TreeNode(27);
        System.out.println(new No98().isValidBST(root));
    }
}
